BZOJ4148【AMPPZ2014】Pillars <构造>

Problem

【AMPPZ2014】Pillars

Time Limit:
Memory Limit:

Description

给定一个的矩形，其中有f个的障碍物，其中任意两个障碍物中心之间的欧几里得距离至少为，
且每个障碍物的中心到边缘的距离至少为。请找到一条从左下角出发经过所有没有障碍物的点各一次的且最后回到左下角的回路。

Input

第一行包含三个整数(且都为偶数)。
接下来行，每行两个整数(, )，表示该障碍物左下角的坐标。

Output

如果无解，输出，否则第一行输出，第二行输出方案。
方案包含个字符，第个字符表示第步的移动方向，用表示上，表示下，表示左，表示右。

Sample Input

1
2
3

12 6 2
3 3
9 3

Sample Output

1 2	TAK PPPPPPPPPPPGGGLDDLLLLLGPPGLLLDDLLLGGGPPPPPPPPPPGLLLLLLLLLLLDDDDD

Hint

标签：构造

Solution

一道很适合构造入门的题。
我看了的题解才想出来。
首先不考虑障碍，构造出一个走过全部格子的走法。由于和均为偶数，一定有解。
然后考虑障碍，对障碍四周的格子的方向进行修改。由于两个障碍间距离至少为，故任两个障碍不会影响，只会有两大类。
具体构造方法参见代码。

Code

#include <bits/stdc++.h>
#define MAX_N 1000
using namespace std;
int n, m, f;	char s[MAX_N+5][MAX_N+5];
int main() {
    scanf("%d%d%d", &n, &m, &f);
    for (int i = 1; i <= n; i++)	for (int j = 1; j <= m; j++)	s[i][j] = i&1 ? 'D' : 'G';
    for (int i = 1; i <= n; i++) {
        if (i^n)	s[i][1] = 'P';
        if ((i^1) && (i&1))	s[i][2] = 'L';
        if (!(i&1))	s[i][m] = 'L';
    }
    for (int i = 0; i < f; i++) {
        int x, y;	scanf("%d%d", &x, &y);
        if (x&1)	s[x][y+2] = 'P', s[x+1][y-1] = 'L', s[x+1][y+2] = 'P', s[x+2][y+3] = 'L';
        else if (y^3)	s[x][y-1] = 'P', s[x+1][y-1] = 'P', s[x+1][y+2] = 'L', s[x+2][y-2] = 'L';
        else	s[x][1] = 'G', s[x][2] = 'P', s[x+1][2] = 'D', s[x+1][5] = 'L';
    }
    puts("TAK");
    for (int x = 1, y = 1, lft = n*m-4*f; lft; lft--) {
        putchar(s[x][y]);
        if (s[x][y] == 'P')	x++;
        else if (s[x][y] == 'L')	x--;
        else if (s[x][y] == 'G')	y++;
        else	y--;
    }
    return 0;
}